Skip to content

Latest commit

 

History

History
69 lines (53 loc) · 2.18 KB

README.md

File metadata and controls

69 lines (53 loc) · 2.18 KB

2478. Number of Beautiful Partitions

You are given a string s that consists of the digits '1' to '9' and two integers k and minLength.

A partition of s is called beautiful if:

  • s is partitioned into k non-intersecting substrings.
  • Each substring has a length of at leastminLength.
  • Each substring starts with a prime digit and ends with a non-prime digit. Prime digits are '2', '3', '5', and '7', and the rest of the digits are non-prime.

Return the number of beautiful partitions ofs. Since the answer may be very large, return it modulo109 + 7.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "23542185131", k = 3, minLength = 2 Output: 3 Explanation: There exists three ways to create a beautiful partition: "2354 | 218 | 5131" "2354 | 21851 | 31" "2354218 | 51 | 31"

Example 2:

Input: s = "23542185131", k = 3, minLength = 3 Output: 1 Explanation: There exists one way to create a beautiful partition: "2354 | 218 | 5131".

Example 3:

Input: s = "3312958", k = 3, minLength = 1 Output: 1 Explanation: There exists one way to create a beautiful partition: "331 | 29 | 58".

Constraints:

  • 1 <= k, minLength <= s.length <= 1000
  • s consists of the digits '1' to '9'.

Solutions (Python)

1. Solution

fromfunctoolsimportcacheclassSolution: defbeautifulPartitions(self, s: str, k: int, minLength: int) ->int: @cachedefsubPartitions(i: int, k: int) ->int: ifk==0: returni==len(s) iflen(s) -i<k*minLengthors[i] notin"2357": return0ret=0forjinrange(i+minLength, len(s) - (k-1) *minLength+1): ifs[j-1] notin"2357": ret= (ret+subPartitions(j, k-1)) %1000000007returnretifs[-1] in"2357": return0returnsubPartitions(0, k)
close